package Sort;

import java.util.Arrays;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: homechen
 * Date: 2024-03-12
 * Time: 13:23
 */
public class mergerSort {
    public static void main(String[] args) {
        int[] array = {1, 3, 4, 2, 5, 6, 2, 35, 3, 3, 55, 1, 3, 14, 53};
        int n = array.length;
        MergerSort(array, 0, n - 1);
        System.out.println(Arrays.toString(array));
    }

    // 整个数组的下标
    private static void MergerSort(int[] array, int left, int right) {
        // 先进行分，再进行归
        if (left >= right) {
            return; // 只有一个元素
        }
        int mid = (right + left) / 2;
        MergerSort(array, left, mid); // 递归左边
        MergerSort(array, mid + 1, right); // 递归右边
        // 单趟递归程序
        _MergerSort(array, left, mid, right);
    }

    private static void _MergerSort(int[] array, int left, int mid, int right) {
        // 开辟新数组进行，存储排序后的结果，再拷贝回到原来数组的位置
        int begin1 = left;
        int begin2 = mid + 1;
        int j = 0;
        int[] tmp = new int[right - left + 1];
        while (begin1 <= mid && begin2 <= right) {
            if (array[begin1] <= array[begin2]) {
                tmp[j++] = array[begin1++];
            } else {
                tmp[j++] = array[begin2++];
            }
        }

        // 可能还有未归并完的数据
        while (begin1 <= mid) {
            tmp[j++] = array[begin1++];
        }

        while (begin2 <= right) {
            tmp[j++] = array[begin2++];
        }

        // 最后将排序好的数据，拷贝回原来数组的位置
        for (int i = 0; i < tmp.length; i++) {
            array[left + i] = tmp[i]; // + left 避免 右边有数据的情况
        }
    }
}
